package book;

public class KnapsackSolution {
    public int knapsack(int n, int c, int[] w, int[] v) {
        int[] dp = new int[c + 1];
        for (int i = 0; i < n; i++) 
            for (int j = c; j >= w[i]; j--) 
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        return dp[c];
    }

    public static void main(String[] args) {
        int n = 5, c = 10;
        int[] w = {2,2,6,5,4}, v = {6,3,5,4,6};
        int ans = new KnapsackSolution().knapsack(n, c, w, v);
        System.out.println("最大价值为: " + ans);
    }
}
